class code3 {
    public int widthOfBinaryTree(TreeNode root) {
        int ret = 0;
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();//数组模拟队列
        q.add(new Pair<TreeNode,Integer>(root,1));

        while(!q.isEmpty()) {
            //先更新这一层的宽度
            Pair<TreeNode,Integer> t1 = q.get(0);
            Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
            ret = Math.max(ret,t2.getValue()-t1.getValue()+1);
            //让下一层进队
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> t:q) {
                TreeNode node = t.getKey();
                Integer index = t.getValue();
                if(node.left!=null) tmp.add(new Pair<TreeNode,Integer>(node.left,2*index));
                if(node.right!=null) tmp.add(new Pair<TreeNode,Integer>(node.right,2*index+1));
            }
            q = tmp;
        }

        return ret;
    }
}